The demand for fast and reliable transmission of digital information has encouraged the development of many different types of communication transceivers (a transmitter and receiver in one element) which efficiently employ the minimal bandwidth of telephone lines. One such communication technique is quadrature amplitude modulation (QAM) and another is pulse-amplitude modulation (PAM).
For both techniques, a sequence of equally likely data symbols is transmitted as pulses over the communication channel at a fixed symbol rate which is significantly above than the bandwidth of the communication channel. As a result, the pulses are delayed and also spread out in time which means that their amplitude diminishes over time. The signal which is received by the receiver is a superposition of the pulses over time. The "memory" of a channel, known as the intersymbol interference (ISI), is then the amount of time, in symbols, in which the transmitted pulse still affects the subsequent pulses.
Furthermore, the communication channel is noisy, typically from cross-talk due to the fact that many conversations are carried over the same telephone cable. The cross-talk is often referred to as "near end Xtalk (NEXT)". Furthermore, the communication transceiver both transmits and receives at the same time. The transmission causes an echo within the signal received by the receiver.
One technique for reducing the effect of the intersymbol interference is the decision-feedback equalizer (DFE). This equalizer assumes that the signal at any one time is the sum of the previous N stretched pulses, where N is the memory of the channel. If the equalizer somehow knows the symbol values for all the previous N-1 stretched pulses, it can remove the influence of the previous N-1 pulses and, from the result, can determine the Nth symbol value. However, if any one decision was incorrect, the later decisions may be incorrect.
For integrated subscriber digital network (ISDN) signals, which are transmitted at 160 Kbits/sec, the memory of the channel is typically 40 symbols. For high bit rate digital subscriber loop (HDSL) signals, which are transmitted at 784 Kbits/sec in the U.S. and at 1168 Kbits/sec in Europe, the memory of the channel is typically 160 symbols. For 2 Mbit/sec channels, the memory of the channel is over 200 symbols.
A maximum likelihood sequence estimator (MLSE), implemented by the Viterbi algorithm, has been suggested to overcome the noise and intersymbol interference problems of high transmission rates over communication channels. The MLSE is the optimal receiver for channels with ISI; however, the MLSE increases in complexity as a function of the channel memory and the size Q of the symbol alphabet. Therefore, the MLSE is not practical for implementation in a real-time, high data rate communication channels with large channel memories and a symbol alphabet larger than 2.
The following three articles discuss different methods for implementing reduced state sequence estimators (RSSE) which reduce the complexity of the Viterbi algorithm but still offer the performance quality of the MLSE.
Vilas Joshi and David D. Falconer, "Sequence Estimation Techniques for Digital Subscriber Loop Transmission with Crosstalk Interference", IEEE Transactions on Communications, Vol. 38, No. 9, September 1990, pp. 1367-1374;
Nambirajan Seshadri and John B. Anderson, "Decoding of Severely Filtered Modulation Codes Using the (M,L) Algorithm", IEEE Journal on Selected Areas in Communication, Vol. 7, No. 6, August 1989, pp. 1007-1016; and
Won U. Lee and F. S. Hill, Jr., "A Maximum-Likelihood Sequence Estimator with Decision-Feedback Equalizers", IEEE Transactions on Communications, Vol. COM-25, No. 9, September 1977, pp. 971-979.
The above literature propose several RSSE estimators. One of them is the (M,L) algorithm which, at every symbol interval, saves M symbol sequences of L symbols which represent M hypotheses of the actual sequence of symbols transmitted by the remote transmitter. At each interval, the algorithm determines which sequence provides the best match to the received signal and outputs the oldest symbol from the best sequence.
At every symbol interval, the sequences are branched to include one of the Q possible symbol levels (i.e. Q*M new sequences are produced). The new sequences are compared and the M best ones are selected.
The methods described in the above articles are complex where the complexity is a function of the sizes of M and L and of the alphabet size as indicated by Q. For example, the signal can be binary modulated and thus, symbols can have two levels (1 and -1). 2B1Q modulation is also popular which has four levels (-3, -1, 1, 3) or more levels. One of the above articles presents results for L=40, M varying from 8 to 32, both binary and quaternary symbol levels and for an ISDN channel (for whom the channel memory is of length 40). Another article presents results for L=30, M=4 or 8, binary symbol level signals. All of these RSSE estimators are complex due to the number and size of the sequences to be calculated. Furthermore, the estimators described do not provide significantly better results to compensate for their increased complexity over standard ISI reducing units.